package java学习.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * @author 刘世锦
 * 2022-12-27 11:18:45	 当前时间
 */
//给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。 
//
// 差值是一个正数，其数值等于两值之差的绝对值。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [4,2,6,1,3]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：root = [1,0,48,null,null,12,49]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目范围是 [2, 104] 
// 0 <= Node.val <= 105 
// 
//
// 
//
// 注意：本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-node
//s/ 相同 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉搜索树 二叉树 
// 👍 409 👎 0

public class 二叉搜索树的最小绝对差{
	public static void main(String[] args) {
		Solution solution = new 二叉搜索树的最小绝对差().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦
	 *  @date  2023/2/9 17:08
	 *
	 *     0  1  2  3
	 *     1 12 48 49
	 */
	public int getMinimumDifference(TreeNode root) {

		if (root==null) return 0;

		int left = getMinimumDifference(root.left);
		if (pre!=null){
			min = Math.min(root.val-pre.val,min);
		}
		pre = root;
		getMinimumDifference(root.right);
		return min;
	}
		public int getMinimumDifferenceByReviewBFS_stack(TreeNode root) {
			int result = Integer.MAX_VALUE;
			// 记录 上一个节点
			TreeNode pre = null;
			Stack<TreeNode> stack = new Stack<>();
			ArrayList<Integer> list = new ArrayList<>();
			if (root != null) {
				while (!stack.isEmpty() || root != null) {
					while (root != null) {
						stack.push(root);
						root = root.left;
					}
					TreeNode node = stack.pop();
//				list.add(node.val);
					if (pre!=null){
						result = Math.min(result,node.val-pre.val);
					}
					pre = node;
					root = node.right;

				}
//			int[] dp = new int[list.size()];
//			dp[0] = result;
//			for (int i = 1; i < list.size(); i++) {
//				dp[i] = Math.min(list.get(i)-list.get(i-1),dp[i-1]);
//			}
//			return dp[list.size()-1];
			}
			return result;
		}
		// 复习end


		int min = Integer.MAX_VALUE;
		TreeNode pre = null;
		public int getMinimumDifferenceDFS(TreeNode root) {
			if (root==null){
				return 0;
			}
			dfs(root);
			return min;
		}

		private void dfs(TreeNode root) {
			if (root==null){
				return;
			}
			dfs(root.left);
			if (pre!=null){
				min = Math.min(min,root.val-pre.val);
			}
			pre = root;
			dfs(root.right);
		}

		/**
		 * 0  1 2  3  4
		 * 0 1 12 48 49
		 *
		 * dp[0] = max
		 * dp[1] = 1
		 * dp[2] = 1,12 1
		 * dp[3] = 1,36 1
		 * dp[4] = 1,1 1
		 *
		 * 1 2 3 4 6
		 * 对升序数组 aa 求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值
		 */
		public int getMinimumDifferenceBFS1(TreeNode root) {
			Stack<TreeNode> stack = new Stack<>();
			ArrayList<Integer> list = new ArrayList<>();
			if (root==null){
				return 0;
			}
			while (!stack.isEmpty()||root!=null){
				while (root!=null){
					stack.push(root);
					root = root.left;
				}
				TreeNode node = stack.pop();
				list.add(node.val);
				root = node.right;
			}
			System.out.println(list);

			int [] dp = new int[list.size()];
			dp[0] = Integer.MAX_VALUE;
			for (int i = 1; i < list.size(); i++) {
				dp[i] = Math.min(dp[i-1],list.get(i)-list.get(i-1));
			}
			System.out.println(Arrays.toString(dp));
			return dp[dp.length-1];

		}

		public int getMinimumDifferenceBFS2(TreeNode root) {
			Stack<TreeNode> stack = new Stack<>();
			int min = Integer.MAX_VALUE;
			TreeNode pre = null;
			if (root==null){
				return 0;
			}
			while (!stack.isEmpty()||root!=null){
				while (root!=null){
					stack.push(root);
					root = root.left;
				}
				TreeNode node = stack.pop();
				if (pre!=null){
					min = Math.min(min,node.val-pre.val);
				}
				pre = node;
				root = node.right;
			}
			return  min;
		}

	}

//leetcode submit region end(Prohibit modification and deletion)

}
